ACM-ICPC北京赛区2018-D-Frog and Portal

题目大意 :
有一只青蛙站在位置0，他可以选择往前跳一步或者两步，他希望跳到位置200上，他有多少种跳法呢? 这其实是个斐波拉契数，如果我们加强难度，假设每个位置上可以创建最多一个传送门，可以传送到任何地方，传送的规则是传送到不能传送为止比方说，位置1上有个传送门，传送到2，2上有门传送到3，3又传送到4，4上没有传送门，于是当青蛙跑到1上的时候，他会被立刻传送到4上，当然他可以选择从0跳过1，一次性跳到2，他就不会进入1的传送门，很可惜，2上面的传送门将它最终送到了4 ，当然如果传送门构成死循环，青蛙就永远无法出来了。
现在要你构造传送门，使得青蛙有恰好k种办法跳到位置200，k在int内

题解展开

题解收起

现首先考虑到两段连续的不含有传送门的位置，中间若只隔着一个i到i到传送门，那么到终点到方案数一定是几个斐波拉契数的积，很遗憾，斐波拉契数不是质数，它不具有像质数集合可以用几个元素的积来构造整数集合一样的性质，这个办法失效
然后我们仔细思考，发现如果位置i的传送门传送到i-1，i-2，i-3。。。这些数的话，方案数是无穷大，
第一段表明只同i->i的传送门不可能完成，第二段表示不能使用或者说不使用传送门i->i-k（k>0）比使用更加优，于是我们得到了一个简单的推论:答案可以由i->i 与i->i+k两者结合得到
紧接着我们开始分析前几个格子的跳跃方案数：
方案 1 1 2 3 5
位置 0 1 2 3 4
考虑在位置3放一个传送门传送到i:
方案 1 1 2 3 2 2 4
位置 0 1 2 3 4 5 6
这个时候我们应该警觉到了,方案数出现了4，出现了4，4不是斐波拉契数。再继续观察，位置3到底怎么回事？他对谁有贡献？
如果我们假设让位置3跳到自己，他会对答案贡献0，如果我们让位置3跳到200，他会对答案贡献3
选或不选+1 2 4的出现，让我们联想到了利用二进制，
然后我们构建了一个周期为6的自动匹配的东西，
方案 1 1 1 1 2 3 ...
位置 0 1 2 3 4 5 ...
绿色代表i->i死循环,红色部分可选死循环或者跳到终点，表示选或不选，6*32=192，我们在最后的地方连续弄两个 i->i就可以保证到达终点的一定是周期内部的方案。于是范围跨度194，传送门稳定66个，就可以根据输入的k的二进制表示来调整红色部分的传送门即可。于是题目被解决了。

代码展开

代码收起

#include <bits/stdc++.h>
using namespace std;

void choose(int i){
    printf("%d %d\n",i+1,199);
    printf("%d %d\n",i+5,i+5);
}


void no_choose(int i){
    printf("%d %d\n",i+1,i+1);
    printf("%d %d\n",i+5,i+5);
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        printf("66\n");
        for(int i=0;i<32;i++){
            if(n&(1<<i)){
                choose(6*i);
            }
            else {
                no_choose(6*i);
            }
        }
        printf("197 197\n");
        printf("198 198\n");
    }
}